// Original source code from http://people.cis.ksu.edu/~huth/301/primes.html

package SecureChat;

import java.math.BigInteger;
import java.util.Random;


public class Miller_Rabin {

  private static final BigInteger ZERO = new BigInteger("0");
  private static final BigInteger ONE = new BigInteger("1");
  private static final BigInteger TWO = new BigInteger("2");

  
  public static boolean is_prime(BigInteger n, int s) {
    BigInteger a;
    for (int i = 1; i <= s; ++i) {
      Random seed = new Random();
      do { a = new BigInteger(n.bitLength()-1, seed);
      } while (a.compareTo(ZERO) <= 0 || a.compareTo(n) >= 0);
      if (witness(a,n)) { return false; }
    }
    return true;
  }

  public static boolean witness(BigInteger a, BigInteger n) {

    BigInteger b = n.subtract(ONE);
    int k = b.bitLength() - 1;
    BigInteger t = new BigInteger("1");
    BigInteger x;

    for (int i = k; i >= 0; --i) {

      x = t;
      t = t.modPow(TWO,n);

      if (t.equals(ONE) && !x.equals(ONE) && !x.equals(b)) return true;
      if (b.testBit(i)) t = t.multiply(a).mod(n);
    }

    if (!t.equals(ONE)) { return true; }
    return false;
  }

}
